#include<bits/stdc++.h>
#define ONLINE_JUDGE
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
const int d[5][2] = { {0,0},{1,0},{-1,0},{0,1},{0,-1} };

int n, m, k, st;
vector<pair<int, int>> p;
vector<int> dp(1 << 20, INF);
set <pair<int, int>> c;
queue<int> q;

int updata(int s, int idx, int v) { return (s & ~(3 << (idx * 2))) | (v << (idx * 2)); }

void solve()
{
    st = 0;
    cin >> n >> m >> k;
    for (int i = 0;i < k;i++) {
        int x, y, w;cin >> x >> y >> w;
        p.push_back({ x,y });
        st = updata(st, i, w);
        for (int i = 0;i < 5;i++) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m)
                c.insert({ nx,ny });
        }
    }
    dp[st] = 0;
    q.push(st);
    while (!q.empty()) {
        int cur = q.front();q.pop();
        if (cur == 0) break;
        for (auto it = c.begin();it != c.end();it++) {//枚举可能的放置方法
            int x = it->first, y = it->second, temp = cur;
            //枚举炸弹范围
            for (int i = 0; i < k; i++)
                for (int j = 0; j < 5; j++)
                    if (x == p[i].first + d[j][0] && y == p[i].second + d[j][1]) {
                        int fish_cnt = (temp >> (i * 2)) & 3;
                        if (fish_cnt > 0) temp = updata(temp, i, fish_cnt - 1);
                    }
            if (dp[temp] > dp[cur] + 1) {
                dp[temp] = dp[cur] + 1;
                q.push(temp);
            }
        }
    }
    cout << dp[0] << '\n';
}

signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    int T = 1;
    //cin>>T;
    for (int i = 1;i <= T;i++) {
        solve();
    }
}